#include "MergeSort.h"
void MergeSort::Distribute(int N)
{     
	int k;
	int i, pa, pb, pc;  
	pa = pb = pc = 0;   while (pa < N)
	{       
		for (i=0; (pa<N) && (i<k); i++, pa++, pb++)
		{        
			b[pb] = a[pa];              
		}       
		for (i=0; (pa<N) && (i<k); i++, pa++, pc++)
		{       
			c[pc] = a[pa];              
		}   
	}   
	nb = pb; nc = pc; 
}

void MergeSort::Merge()
{    

	int k;
	int pa, pb, pc;  
	pa = pb = pc = 0; 
	Distribute(n);
	while ((pb < nb) && (pc < nc))
	{       
		MergeSubarr(nb, nc, pa, pb, pc, k);  
	}   
	while (pb < nb)
	{       
		a[pa ++] = b[pb ++];
	}  
	while (pc < nc)
	{       
		a[pa ++] = c[pc ++];
	} 
}

void MergeSort::MergeSubarr(int nb, int nc, int &pa, int &pb, int &pc, int k)
{    
	int rb, rc;   rb = min(nb, pb+k);     
	rc = min(nc, pb+k); 
	while ((pb < rb) && (pc < rc))
	{      
		if (b[pb] < c[pc])  
			a[pa ++] = b[pb ++];   
		else   a[pa ++] = c[pc ++];     
	}  
	while (pb < rb)
	{     
		a[pa ++] = b[pb ++];    
	}   
	while (pc < rc)
	{       
		a[pa ++] = c[pc ++];
	}
}